package com.xiaoyu.bitOperation;

/**
 * @program: DS_and_A
 * @description: 二进制字符串求和
 *
 * 有定理 ---> 设a，b为两个二进制数，则a+b = a^b + (a&b)<<1。
 *                                  a^b计算无进位和 ,(a&b)计算进位,然后左移让进位在它应该在的地方
 *
 * 给你两个二进制字符串，返回它们的和（用二进制表示）。
 *
 * 输入为 非空 字符串且只包含数字 1 和 0。
 *
 * 输入: a = "1010", b = "1011"
 * 输出: "10101"
 *
 * @author: YuWenYi
 * @create: 2021-05-12 11:09
 **/
public class AddBinary_67 {
    public static String addBinary(String a, String b) {
        String maxStr = a.length() > b.length() ? a : b;
        String minStr = a.length() < b.length() ? a : b;

        int diff = maxStr.length() - minStr.length();
        //如果两个字符串长度不一样,就给字符串长度较小的字符串补0
        if (diff > 0){
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < diff; i++) {
                sb.append("0");
            }
            sb.append(minStr);

            a = maxStr;
            b = sb.toString();
        }

        StringBuilder res = new StringBuilder();

        int carry = 0;
        for (int i = maxStr.length() - 1; i >= 0; i--) {
            if (a.charAt(i) == '1' && b.charAt(i) == '1'){
                if (carry == 1){
                    res.append("1");
                }else {
                    res.append("0");
                }
                carry = 1;
            }else if (a.charAt(i) == '0' && b.charAt(i) == '0'){
                if (carry == 1){
                    res.append("1");
                    carry = 0;
                }else {
                    res.append("0");
                }
            }else {
                if (carry == 1){
                    res.append("0");
                }else {
                    res.append("1");
                }
            }
        }
        if (carry == 1)
            res.append("1");
        return res.reverse().toString();
    }


    //官方题解1:调用API --> 对于超大值的用例,无法解析
    public static String addBinary1(String a, String b) {
        return Long.toBinaryString(Long.parseLong(a,2) + Long.parseLong(b,2));
    }

    public static void main(String[] args) {
        String a = "1010000011100001101";
        String b = "1101010010111011001100000011011110011"; //10000
        String sum = addBinary1(a, b);
        System.out.println(sum);
    }

}
